(a) Field of the Invention
The present invention relates to a decoding technology for channel codes. More particularly, the present invention relates to a message-passing decoder for LDPC (Low-Density Parity-Check) codes that receives data encoded with LDPC codes on a channel, having a consecutive output values, and decodes the coded data using a message-passing decoding algorithm.
(b) Description of the Related Art
LDPC codes are linear block codes reported by Gallager in 1962, and they are defined as a sparse parity-check matrix of which the elements are mostly “0”. LDPC codes were out of the public's mind for a long time due to expense of implementation, but they were re-discovered by MacKay and Neal in 1995. In 1998, irregular LDPC codes derived from generalization of the LDPC codes proposed by Gallager were announced. At the time of the first announcement of the LDPC codes by Gallager, the probabilistic coding method for LDPC codes was also made known, through which method the excellent performance of LDPC codes was demonstrated. It was also found that LDPC codes have an improved performance when they are expanded from binary codes to nonbinary codes. Like Turbo codes, LDPC codes have a bit error rate (BER) approaching the channel capacity limit defined by Shannon. The irregular LDPC codes known to have the greatest performance are suitable for applications requiring a high-quality transmission environment having a considerably low BER, because they need no more than 0.13 dB in addition to the channel capacitor by Shannon in order to achieve a BER of 10−6 when the block size is about 106 bits in the additive white Gaussian noise (AWGN) channel environment.
The basic decoding method for LDPC codes includes a probabilistic decoding algorithm, unlike the algebraic decoding algorithm that is the decoding method of the conventional block codes, and adapts a belief propagation method based on graph theory and probabilistic prediction theory. Accordingly, the LDPC decoder calculates, for individual bits of the code word received through the channel, the probability of the corresponding bit being “1” or “0”. The probabilistic information calculated by the decoder is specifically called a “message”, and is used in checking whether or not each parity defined in a parity-check matrix is satisfied. The message calculated when a specific parity of the parity-check matrix is satisfied, i.e., when the result of the parity check is “0”, is specifically called a “parity-check message”, which specifies the value of each bit of the code word. The parity-check message for each parity is used in determining the value of the corresponding bit. The information about the bit calculated is called a “bit message”. In the procedure of repeating the message-passing operation, information about the bits of each code word is constantly improved until all the parities of the parity-check matrix are satisfied. If the parities of the parity-check matrix are all satisfied, the decoding of the code word is ended. Typically, systematic codes are used in a channel environment having a low signal-to-noise ratio (SNR), so a specific part of the code word is extracted to reproduce information bits. It is favorable to convert a probabilistic message to a log likelihood ratio (LLR) message for calculation so as to readily achieve message propagation decoding of LDPC binary codes in the AWGN channel environment.
This LLR message decoding method involves a logarithm function operation in message calculation, and it causes a problem in regard to implementation of a nonlinear function. Typically, in calculation of a nonlinear function for an integrated circuit, a specific value is stored in a read-only memory (ROM) and the output value of an address related to the input is read out from the ROM. The use of this method requires memories of a large capacity and increases the area cost of the integrated circuit, thereby raising the cost of implementation. But, reducing the number of bits representing input and output deteriorates the accuracy of the message calculation to reduce the entire decoding performance and increase the BER.